"use strict";
{
    class Node {
        constructor(data = null, Left = null, right = null) {
            this.data = data;
            this.Left = Left;
            this.right = right;
        }
        show() {
            return this.data;
        }
    }
    class BST {
        constructor(root = null) {
            this.root = root;
        }
        insert(data) {
            let node = new Node(data, null, null);
            // 如果根为空 直接插入
            if (this.root === null) {
                this.root = node;
                return;
            }
            // 根据二叉搜索树规则插入
            let current = this.root;
            let parent;
            while (true) {
                parent = current;
                if (parent.data && data < parent.data) {
                    current = current.Left;
                    if (!current) {
                        parent.Left = node;
                        break;
                    }
                }
                else {
                    current = current.right;
                    if (!current) {
                        parent.right = node;
                        break;
                    }
                }
            }
        }
        // 先序遍历
        preOrder(root) {
            if (root) {
                console.log(root.data);
                this.preOrder(root.Left);
                this.preOrder(root.right);
            }
        }
        // 中序遍历
        inOrder(root) {
            if (root) {
                this.inOrder(root.Left);
                console.log(root.data);
                this.inOrder(root.right);
            }
        }
        // 后续遍历
        postOrder(root) {
            if (root) {
                this.postOrder(root.Left);
                this.postOrder(root.right);
                console.log(root.data);
            }
        }
        // 获取最小值
        getMin() {
            let current = this.root;
            while (current && current.Left) {
                current = current.Left;
            }
            return (current && current.data);
        }
        // 获取最大值
        getMax() {
            let current = this.root;
            while (current && current.right) {
                current = current.right;
            }
            return (current && current.data);
        }
        // 查找节点
        find(data) {
            let current = this.root;
            while (current) {
                if (current && current.data === data) {
                    return current;
                }
                else if (current && current.data < data) {
                    current = current.right;
                }
                else if (current && current.data > data) {
                    current = current.Left;
                }
            }
            return null;
        }
        // 删除节点
        remove(data) {
            this.root = this.removeNode(this.root, data);
        }
        removeNode(node, data) {
            if (!node) {
                return null;
            }
            if (data === node.data) {
                // 叶子节点
                if (!node.Left && !node.right) {
                    return null;
                }
                // 没有左节点
                if (!node.Left) {
                    return node.right;
                }
                // 没有右节点
                if (!node.right) {
                    return node.Left;
                }
                // 有两个子节点的节点
                let tempNode = this.getMinNode(node.right);
                node.data = tempNode.data;
                node.right = this.removeNode(node.right, tempNode.data);
                return node;
            }
            else if (data < node.data) {
                node.Left = this.removeNode(node.Left, data);
                return node;
            }
            else {
                node.right = this.removeNode(node.right, data);
                return node;
            }
        }
        getMinNode(node) {
            let current = node;
            while (current && current.Left) {
                current = current.Left;
            }
            return current;
        }
    }
    let nums = new BST();
    // nums.root
    nums.insert(23);
    nums.insert(45);
    nums.insert(16);
    nums.insert(37);
    nums.insert(3);
    nums.insert(99);
    nums.insert(22);
    // nums.inOrder(nums.root as Node)
    nums.preOrder(nums.root);
    // nums.postOrder(nums.root as Node)
    console.log('min', nums.getMin());
    console.log('max', nums.getMax());
    console.log('find', nums.find(7));
    nums.remove(23);
    // nums.preOrder(nums.root as Node)
    // nums.inOrder(nums.root as Node)
}
